package com.example.demo.algorithm.graph;

import com.example.demo.algorithm.linear.Stack;

/**
 * 深度优先搜索节点排序
 */
public class DepthFirstOrder {
    //索引代表定点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //使用栈，存储顶点序列
    private Stack<Integer> reversePost;

    public DepthFirstOrder(Digraph g) {
        //初始化marked数组
        this.marked = new boolean[g.V()];
        //初始化reversePost栈
        this.reversePost = new Stack<Integer>();
        //遍历图中的每一个顶点，让每个顶点作为入口，完成一次深度优先搜索
        for (int v = 0; v < g.V(); v++) {
            if (!marked[v]) {
                dfs(g, v);
            }
        }
    }

    //基于深度优先搜索，检测图g中是否有环
    private void dfs(Digraph g, int v) {
        //标记当前v已经被搜索
        marked[v] = true;
        //通过循环深度搜索顶点v
        for (Integer w : g.adj(v)) {
            //如果当前顶点w没有被搜索，则递归调用dfs进行搜索
            if (!marked[w]) {
                dfs(g, w);
            }
        }
        //让顶点v进栈
        reversePost.push(v);
    }

    //获取顶点栈线性序列
    public Stack<Integer> reversePost() {

        return reversePost;
    }


}
